package com.zhangxiaofanfan.hotcode.third;

import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-100-liked">两数相加</a>
 *
 * @author zhangxiaofanfan
 * @date 2024-05-28 22:47:32
 */
public class HotCode028 {
    public static void main(String[] args) {
        HotCode028 hotCode028 = new HotCode028();
        ListNode l1 = new ListNode(9);
        l1.next = new ListNode(9);
        ListNode l2 = new ListNode(9);
        hotCode028.addTwoNumbers(l1, l2);
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        Stack<ListNode> stack1 = traverseListNode(l1);
        Stack<ListNode> stack2 = traverseListNode(l2);
        int carry = 0;
        int addend1 = 0;
        int addend2 = 0;
        int sum = 0;
        ListNode result = new ListNode();
        ListNode temp;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            addend1 = stack1.isEmpty() ? 0 : stack1.pop().val;
            addend2 = stack2.isEmpty() ? 0 : stack2.pop().val;
            sum = addend1 + addend2 + carry;
            temp = new ListNode();
            temp.val = sum % 10;
            carry = sum / 10;
            temp.next = result.next;
            result.next = temp;
        }
        if (carry != 0) {
            temp = new ListNode();
            temp.val = carry;
            temp.next = result.next;
            result.next = temp;
        }
        return result.next;
    }

    public Stack<ListNode> traverseListNode(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        return stack;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
